# Лабораторная работа № 2 Алгоритмы обхода графа
Цель: выработать навык различных способов представления графов
Постановка задачи
Генерируется случайный связный неориентированный граф без петель и кратных
рёбер в одном из четырёх представлений. Выполняется преобразование графа из одного
представления в другое. Выполняется обход графа в глубину и в ширину в каждом из
представлений. Определить время выполнения алгоритмов.
Представления:
    1. Список рёбер (вектор пар вершин)
    2. Матрица смежности (вектор векторов)
    3. Список смежных вершин (вектор списков)
    4. Матрица инцидентности (вектор векторов) 
Генерируется: 
    • количество вершин n – от 20 до 30, 
    • рёбер – доля от максимального количества n(n-1)/2
Генерация - 
матрица смежности
        ◦ для каждой вершины – количество смежных, потом смежные
список смежных вершин
        ◦ для каждой вершины – количество смежных, потом смежные
список рёбер
        ◦ для каждого ребра – левая и правая вершина из списка вершин
матрица инцидентности
        ◦ для каждого ребра – левая и правая вершины из списка вершин
Преобразования:
	1 -> 234
	2 -> 134
	3 -> 124
	4 -> 123
12 13 14 21 23 24 31 32 34 41 42 43 – 12 преобразований
Вычисления по графу
Степени вершин
Порядок выполнения работы
        1.Сгенерировать количество вершин и рёбер
        2.В соответствии с вариантом сгенерировать остальные данные
        3.Вывести сгенерированное представление в текстовый файл Graph
        4.Выполнить обход графа в глубину; последовательность посещаемых вершин вывести
        в тот же файл Graph в одну строку через пробел
        5. Выполнить преобразование
        6. Вывести сгенерированное представление в текстовый файл Graph1
        7. Выполнить обход графа в ширину; последовательность посещаемых вершин вывести
        в тот же файл Graph1 в одну строку через пробел; определить диаметр графа
Вариант 9

n | Представление       |   Преобразование          |   Поиск в глубину         |       Поиск в ширину                  |
9 | Матрица смежности   |   В список смежных вершин |   На матрице смежности    |       На списке смежных вершин        |

# Задача
Сгенерировать связный граф, затем:
2. Представить как матрицу смежности и произвести поиск в глубину
2. Преобразовать в список смежных вершин и произвести поиск в ширину